BST Search | Data Structure | Pusan National University

세 가지 비교 결과x < u.key이면 왼쪽, x > u.key이면 오른쪽 자식 노드로 가고, 같으면 현재 노드에서 성공한다.

버리는 부분 트리한 번 비교할 때마다 현재 노드와 반대쪽 부분 트리 전체를 더 보지 않는다.

실패 탐색가야 할 자식 노드 자리가 None이면 멈춘다. 마지막 노드와 그 빈 방향이 새 키가 들어갈 위치다.

O(높이)경로는 루트에서 아래로만 내려가므로 방문 노드 수는 높이 + 1을 넘지 않는다.

한 번 비교할 때마다 부분 트리 하나를 통째로 버린다

찾는 키를 고르고 진행한 단계를 옮기면 현재 노드, 지나온 경로, 더 이상 볼 필요가 없어진 노드가 바뀐다. 트리는 8, 3, 12, 1, 6, 10, 14의 일곱 키를 가진 BST다.

찾는 키 6

진행한 단계 0

초록 원이 지금 비교하는 노드, 옅은 파란 원과 굵은 초록 선이 지나온 경로다. 흐린 점선 원은 앞선 비교로 더 볼 필요가 없어진 노드이고, 빨간 점선 상자는 가야 할 자식 노드 자리가 비어 있는 곳이다. 원 옆 글자는 그 노드에서의 비교 결과다.

같은 일곱 키를 두 모양으로 연결했다. 모양과 찾는 키를 바꾸면 그 키까지의 경로와 키마다의 방문 노드 수 막대가 바뀐다.

트리 모양

찾는 키

왼쪽은 트리이며 초록 선이 찾는 키까지의 경로다. 오른쪽 막대는 각 키를 찾을 때까지 비교한 노드 수이고 초록 막대가 지금 찾는 키다.

찾는 키와 진행한 단계를 바꾸면 왼쪽에서는 쌓인 _get 호출이, 오른쪽에서는 반복문의 node 변수가 바뀐다. 각 노드에 저장한 값은 "v" 뒤에 키를 붙인 문자열이다.

찾는 키

진행한 단계 1

코드의 초록 줄이 이번 단계에서 실행한 줄이다. 왼쪽 아래 상자는 아래에서 위로 쌓인 _get 호출이고 초록 상자가 맨 위 호출이다. 오른쪽 아래 칸은 node 변수가 가리킨 노드를 차례로 적은 것이며 빨간 상자는 None이다.